找出一个数组中的重复元素(其它元素只出现一次)

Find the Duplicate Number

link
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

题目大意，一个数组包含n+1个整数，这n个整数的范围为[1, n],其中有一个数多次出现(>=2),其它的数均出现一次或者不出现，求出那个重复的数。

解法一:二分法,复杂度$ O(nlogn) $
http://www.cnblogs.com/grandyang/p/4843654.html
在这个数组中，如果一个数出现多次，那么在整个数组中<=这个数的数的数量会大于这个数。什么意思了，假设这个数组中所有的数字都出现了，那么一定有一个数出现了两次。
[1,2,3,..,i,,n],在这里假设i出现了两次，那么在整个数组中，<=i的数字的个数为i+1个，现假设其中的一些数字没出现，那么这些数字被i代替，上面的条件仍然成立。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        //此处直接判断的是数，而不是数组的下标
        int left = 1, right = nums.size()-1;
        
        while(left < right){
            int count = 0;
            int mid = (left + right)/2;
            for(auto a:nums){
                if(a <= mid)  count++;
            }
            if(count <= mid) left = mid +1;
            else right = mid;
        }
        return left;
    }
};

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        //此处直接判断的是数，而不是数组的下标
        int left = 1, right = nums.size()-1;
        
        while(left <= right){
            int count = 0;
            int mid = (left + right)/2;
            for(auto a:nums){
                if(a <= mid)  count++;
            }
            if(count <= mid) left = mid +1;
            else right = mid -1 ;
        }
        return left;
    }
};

解法二:映射找环法
环检测
思路:解决本题需要的主要技巧就是要注意到：由于数组的n + 1个元素范围从1到n，我们可以将数组考虑成一个从集合{1, 2, …, n}到其本身的函数f。这个函数的定义为f(i) = A[i]。基于这个设定，重复元素对应于一对下标i != j满足 f(i) = f(j)。我们的任务就变成了寻找一对(i, j)。一旦我们找到这个值对，只需通过f(i) = A[i]即可获得重复元素。

但是我们怎样寻找这个重复值呢？这变成了计算机科学界一个广为人知的“环检测”问题。问题的一般形式如下：给定一个函数f，序列x_i的定义为

x_0     = k       (for some k)
x_1     = f(x_0)
x_2     = f(f(x_0))
...
x_{n+1} = f(x_n)

假设函数f从定义域映射到它本身，此时会有3种情况。首先，如果定义域是无穷的，则序列是无限长并且没有循环的。例如，函数 f(n) = n + 1，在整数范围内满足这个性质 - 没有数字是重复的。第二，序列可能是一个闭合循环，这意味着存在一个i使得x_0 = x_i。在这个例子中，序列在一组值内无限循环。第三，序列有可能是的“ρ型的”，此时序列看起来像下面这样：

x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                   ^                       |
                   |                       |
                   +-----------------------+

也就是说，序列从一列链条型的元素开始进入一个环，然后无限循环。我们将环的起点称为环的“入口”。

通俗讲就是:
如果数组中元素不重复，那么,任意下标i和数组中该下标的值一一对应，如对于数组 3,4,1,2，有如下对应关系：（注意，值从1~n）

0 – > 2
1  -> 4
2  -> 1
3  -> 3

设这个对应关系的运算函数为f(n) ，那么，我们从下标0出发，每次根据f取出下标i对应的值x，并将这个x作为下一次的下标，直到下标越界。

如3，4，1，2这个数组，那么有 0 – > 2-> 1-> 4(这里带来的困惑是在没有重复的情况下，取不到3)

但如果有重复的话，中间就会产生多个映射，如3,4,1,2,2

0 – > 2
1  -> 4
2  -> 1
3  -> 3
4  -> 2

0 -> 2 -> （1 -> 4-> 2-> 1 -> 4-> 2)
利用龟兔算法,详细见Linked List Cycle

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int turtle = nums[0];
        int hare = nums[nums[0]];
        
        while(hare != turtle){
            hare = nums[nums[hare]];
            turtle = nums[turtle];
        }
        
        turtle = 0;
        while(hare != turtle){  
            turtle = nums[turtle];  
            hare = nums[hare];
        } 
        return hare; 
    }
};

参阅:
http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/
https://segmentfault.com/a/1190000003817671